#include <iostream>

struct ListNode {
    int val;
    ListNode* next;
    ListNode(): val(0), next(nullptr) {};
    ListNode(int x): val(x), next(nullptr) {};
};

/**
 * 快慢指针
 * 快指针每次走2格，慢指针每次走1格
 * 那么，他们相对速度是1格，所以快指针一定会在某时刻和慢指针重叠相遇
 * 
 * https://programmercarl.com/0142.%E7%8E%AF%E5%BD%A2%E9%93%BE%E8%A1%A8II.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
 * 
 * 
 */
ListNode* detectCycle(ListNode* head) {
    ListNode *fast = head, *slow = head;
    while (fast != nullptr && fast->next != nullptr) {
        fast = fast->next->next;
        slow = slow->next;
        if (slow == fast) {
            ListNode* index1 = head;
            ListNode* index2 = fast;
            while (index1 != index2) {
                index1 = index1->next;
                index2 = index2->next;
            }

            return index1;
        }
    }

    return nullptr;
}

int main() {


    return 0;
}